package cn.cxq.learning.math;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 剑指offer
 * 数据流中的中位数
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：352789
 * 本题知识点： 排序 堆
 * 算法知识视频讲解
 * 题目描述
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 */
public class Median {

    // 思路： 看了题解，网上看了csdn学习了一个新的高级数据结构之后，决定使用优先队列解决中位数问题。
    // 思路：初始化一个大顶堆，一个小顶堆，小顶堆存的数永远大于大顶堆的数,而且大顶和小顶都是靠中间的两个数（使大顶堆和小顶堆大小差保持在1之内）
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }); // lambda表达式不知道为什么会慢很多。。。

    int count = 0;

    public void Insert(Integer num) {
        if (count % 2 == 0) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
            count++;
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
            count++;
        }
    }

    public Double GetMedian() {

        if (count == 0) {
            return 0.0;
        }

        if (count % 2 == 0) {
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            return (double) minHeap.peek();
        }
    }

    // 思路： 调用Java的库函数实现排序，然后取出中位数
//    ArrayList<Integer> stream = new ArrayList<>();
//
//    public void Insert(Integer num) {
//        stream.add(num);
//        stream.sort(Comparator.comparingInt(value -> value));
//    }
//
//    public Double GetMedian() {
//
//        if (stream.size() == 0) {
//            return 0.0;
//        }
//
//        double result = 0;
//
//        if (stream.size() % 2 == 0) {
//            result = (double) (stream.get(stream.size() / 2 - 1) + stream.get(stream.size() / 2)) / 2; // 这里记得一定要先转double再做除法。
//        } else {
//            result = stream.get(stream.size() / 2);
//        }
//
//        return result;
//    }
}
